import java.util.*;

/*
    692. 前K个高频单词
    优化：可以用哈希表+小根堆+写比较器
    当堆中元素数目大于k，则弹出一个
 */

public class TopKFrequent {

    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        ArrayList<String> list = new ArrayList<>(Arrays.asList(words));
        for (int i = 0; i < list.size(); i++) {
            String temp = list.get(i);
            int val = map.getOrDefault(temp, 0) + 1;
            map.put(temp, val);
            if (val > 1) {
                list.remove(i);
                i--;
            }
        }
        Collections.sort(list, new Comparator<String>() {
            @Override
            public int compare(String a, String b) {
                int i = map.get(a);
                int j = map.get(b);
                if (i != j) {
                    return i - j;
                } else {
                    return b.compareTo(a);
                }
            }
        });
        ArrayList<String> ans = new ArrayList<>();
        for (int i = list.size() - 1; i >= list.size() - k; i--) {
            ans.add(list.get(i));
        }
        return ans;
    }
}
